This invention relates to the field of software for designing digital circuits, and specifically to systems and method for optimizing digital circuit designs. Designers of digital circuits often use Electronic Design Automation (EDA) software to create digital circuit designs. The EDA software then processes or compiles the digital circuit design to create data that specifies an implementation of the digital design in hardware. This data can include mask layout and other semiconductor processing parameters for implementing the digital design in an integrated circuit. This data may alternately specify data that implements the digital design in a programmable device, such as a programmable logic device (PLD), field programmable gate array (FPGA), or structured or unstructured ASIC.
Typically, digital circuits are described by designers as a network of combinational logic elements, registers, and hierarchical blocks or cells of lower-level circuits. It is often the case that these networks contain redundant elements. For example, redundant elements might be introduced when designers create multiple instances of the same hierarchical cell. It may be the case that two of more instances of a hierarchical cell could share all or a portion of their lower-level circuit. Redundant elements can also be introduced to a digital design through mistakes or carelessness. Redundant elements increase the area or amount of resources needed to implement the digital design and the power consumed by the digital design. Redundant elements can also decrease the speed of the digital design.
Previous techniques of removing redundant logic have focused on identifying equivalent combinational logic using structural and Boolean techniques. For example, structural techniques consider two logic gates to be equivalent if they are fed by the same gates or primary inputs, including potentially ignoring the input order for those gates whose function are independent of the input ordering, such as OR, AND, or XOR gates. Boolean techniques convert all or a subset of the combinational gates in the digital design to a canonical format, such as a Binary Decision Diagram (BDD), which is used to identify equivalent subsets of combinatorial gates. Registers are considered equivalent if the logic feeding their corresponding inputs are the same, otherwise they are treated as primary inputs.
When two or more nodes are identified as equivalent, all but one of the equivalent nodes can be removed from the digital design. The destinations fed by the removed nodes are modified to be fed by the remaining equivalent node. These techniques can be iterated over the modified digital design until no more equivalent nodes are identified.
However, these prior techniques are not capable of identifying equivalent registers in complex netlists in which registers feed back on one another. An example of registered feedback is when the output of a register is provided as an input to combinatorial logic connected with the input of the register. Registered feedback is very common in digital circuits.
It is therefore desirable for a system and method to identify and remove redundant elements of a digital design. It is further desirable for the system and method to be capable of identifying and removing redundant elements in a digital design even in the presence of registered feedback.